timsort: Add gtk_tim_sort_set_runs()
authorBenjamin Otte <otte@redhat.com>
Sat, 11 Jul 2020 04:02:58 +0000 (06:02 +0200)
committerBenjamin Otte <otte@redhat.com>
Wed, 22 Jul 2020 12:04:40 +0000 (14:04 +0200)
commitcbad8ec2e421e0bb7e610cbfe7cf46bc8127da74
tree0fc9fd7103f2b53f00b9d504ef03f1beda07b371
parent800170b47dfede5e9de300eaed630ddebd5c27de
timsort: Add gtk_tim_sort_set_runs()

... and use it in the SortListModel

Setting runs allows declaring already sorted regions so the sort does
not attempt to sort them again.

This massively speeds up partial inserts where we can reuse the sorted
model as a run and only resort the newly inserted parts.

Benchmarks:

    appending half the model
                    qsort  timsort
    128,000 items    94ms     69ms
    256,000 items   202ms    143ms
    512,000 items   488ms    328ms

    appending 1 item
                    qsort  timsort
      8,000 items   1.5ms    0.0ms
     16,000 items   3.1ms    0.0ms
              ...
    512,000 items     ---    1.8ms
gtk/gtksortlistmodel.c
gtk/gtktimsort-impl.c
gtk/gtktimsort.c
gtk/gtktimsortprivate.h